package lcr;

import java.util.ArrayDeque;

public class Test0183 {
    public static void main(String[] args) {
        Solution0183_1 solution = new Solution0183_1();
        int[] ans = solution.maxAltitude(new int[]{4, -2}, 2);
        for (int i : ans) {
            System.out.println(i);
        }
    }
}

class Solution0183_1 {
    public int[] maxAltitude(int[] heights, int limit) {
        int length = heights.length;
        if (length == 0) return new int[0];

        int[] ans = new int[length - limit + 1];

        ArrayDeque<Integer> deque = new ArrayDeque<>();
        deque.add(heights[0]);
        for (int i = 1; i < limit; i++) {
            int height = heights[i];

            while (!deque.isEmpty()&&height > deque.peekLast())
                deque.pollLast();

            deque.offer(height);
        }

        for (int i = 0; i+limit < length; i++) {
            Integer oldMax = deque.peek();
            ans[i]= oldMax;

            int oldHeight = heights[i];
            int newHeight = heights[i + limit];

            if (oldHeight == oldMax) deque.poll();
            while (!deque.isEmpty()&&newHeight > deque.peekLast())
                deque.pollLast();
            deque.offer(newHeight);
        }
        ans[length-limit] = deque.peek();

        return ans;
    }
}
